from config import *
from mysql2graph import *
from tsp import *
import sys
import getopt
import json

def usage():
    print("Usage: python3 %s -n lines number"%(sys.argv[0]))
    print('   -n,--number            the number of path(number must large zero)')
    sys.exit()

def getparams(argv):
    try:
        options, args = getopt.getopt(argv, "hn:", ["help", "number="])
    except getopt.GetoptError:
        usage()
        sys.exit()
    number = ""
    for opts, value in options:
        if opts in ("-h", "--help"):
            usage()
        if opts in ("-n", "--number"):
            number = value
    if number:
        try:
            n = int(number)
            if n > 0:
                return n
            sys.exit(-1)
        except:
            usage()
            sys.exit(-1)
    else:
        usage()
        sys.exit(-1)

def findOddVertex():
    oddList = []
    for i in range(len(Graph)):
        count = 0
        for j in range(len(Graph)):
            if Graph[i][j] == 1:
                count += 1
        if (count % 2) != 0:
            oddList.append(i)
    return oddList

#def combinaOddVertex(oddList):
#    doubleOdds = []
#    for i in range(len(oddList)):
#        for j in range(i,len(oddList)):
#            if i == j:
#                continue
#            childDoubleOdd = []
#            childDoubleOdd.append(oddList[i])
#            childDoubleOdd.append(oddList[j])
#            #print(childDoubleOdd)
#            doubleOdds.append(childDoubleOdd)
#    return doubleOdds

def findStartVertex():
    for i in range(len(Graph)):
        deg = 0
        for j in range(len(Graph)):
            if Graph[i][j]:
                deg += 1
        if (deg%2) != 0:
            return i
    return 0

def edgeCount(GAmap):
    count = 0
    for i in range(len(GAmap)):
        for j in range(i,len(GAmap)):
            if GAmap[i][j]:
                count+=1
    return count

def isBridge(m,n,GAmap):
    deg = 0
    for i in range(len(GAmap)):
        if (GAmap[n][i]):
            deg += 1
    if deg > 1:
        return 0
    return 1

def dfs(prev,start,visited,GAmap):
    count = 1;
    visited[start] = True
    for u in range(len(GAmap)):
        if prev != u:
            if not visited[u]:
                if GAmap[start][u]:
                    count += dfs(start,u,visited,GAmap)
    return count

def fleuryAlgorithm(start,path,GAmap):
    edge = edgeCount(GAmap)
    global v_count
    for v in range(len(GAmap)):
        if GAmap[start][v]:
            visited = [0 for i in range(len(GAmap))]
            if isBridge(start,v,GAmap):
                v_count -= 1
            cnt = dfs(start,v,visited,GAmap)
            if abs(v_count - cnt) <= 2:
                middlePath = []
                middlePath.append(start)
                middlePath.append(v)
                path.append(middlePath)
                #print(start,"-->",v)
                if isBridge(v,start,GAmap):
                    v_count -= 1
                GAmap[v][start] = GAmap[start][v] = 0
                edge -= 1
                fleuryAlgorithm(v,path,GAmap)

def floydQarshall(graph):
    for o in range(len(graph)):
        for p in range(len(graph)):
            for q in range(len(graph)):
                if(graph[p][o] < gigantic and graph[o][q] < gigantic and graph[p][q] > graph[p][o] + graph[o][q]):
                    graph[p][q] = graph[p][o] + graph[o][q]

def createRelationMap():
    RelationMap = []
    for i in range(len(OriginGraph)):
        childRelationMap = []
        for j in range(len(OriginGraph)):
            if OriginGraph[i][j] > 0 and OriginGraph[i][j] < gigantic:
                childRelationMap.append(1)
            else:
                childRelationMap.append(0)
        RelationMap.append(childRelationMap)
    return RelationMap

def replicateGraph():
    tmpGraph = []
    for i in range(len(OriginGraph)):
        childTmpGraph = []
        for j in range(len(OriginGraph)):
            childTmpGraph.append(OriginGraph[i][j])
        tmpGraph.append(childTmpGraph)
    return tmpGraph

def findGAStartVertex(GAList):
    if len(GAList) == 2:
        return GAList[0],GAList[1]
    distance = GACalculateGraph[GAList[0]][GAList[1]]
    start = GAList[0]
    end = GAList[1]
    #print(distance)
    for i in range(int(len(GAList)/2) - 1):
        if distance < GACalculateGraph[GAList[(1+i)*2]][GAList[(i+1)*2+1]]:
            distance = GACalculateGraph[GAList[(1+i)*2]][GAList[(i+1)*2+1]]
            #print(distance)
            start = GAList[(i+1)*2]
            end = GAList[(i+1)*2 + 1]
    remainList = GAList.remove(start)
    remainList = GAList.remove(end)
    return start,end

def GANewRelationMap(GAList):
    GARelationGraph = []
    for i in range(len(Graph)):
        tmpGA = []
        for j in range(len(Graph)):
            tmpGA.append(Graph[i][j])
        GARelationGraph.append(tmpGA)
    #print(GAList)
    for k in range(int(len(GAList)/2)):
        if Graph[GAList[k*2]][GAList[k*2+1]] == 0:
            GARelationGraph[GAList[k*2]][GAList[k*2+1]] = GARelationGraph[GAList[k*2+1]][GAList[k*2]] = 1
        if Graph[GAList[k*2]][GAList[k*2+1]] == 1:
            GARelationGraph[GAList[k*2]][GAList[k*2+1]] = GARelationGraph[GAList[k*2+1]][GAList[k*2]] = 0
    return GARelationGraph
    
def dijkstra(graph,src):
    length = len(graph)
    nodes = [i for i in range(length)]
    visited = [src]
    path = {src:{src:[]}}
    nodes.remove(src)
    distance_graph = {src:0}
    pre = next = src
    while nodes:
        distance = float('inf')
        for v in visited:
             for d in nodes:
                new_dist = graph[src][v] + graph[v][d]
                if new_dist <= distance:
                    distance = new_dist
                    next = d
                    pre = v
                    graph[src][d] = new_dist
        path[src][next] = [i for i in path[src][pre]]
        path[src][next].append(next)
        distance_graph[next] = distance
        visited.append(next)
        nodes.remove(next)
    return distance_graph, path

def addPath(PathRoute,DJList,index):
    for m in range(len(DJList) - 1):
        djTmpPath = [DJList[m],DJList[m+1]]
        PathRoute.insert(index+m,djTmpPath)

def reorganizePath(PATH,OddList,Graph):
    for i in range(int(len(OddList)/2)):
        if Graph[OddList[2*i]][OddList[2*i+1]] == 1:
            repeathPathA = [OddList[2*i],OddList[2*i+1]]
            repeathPathB = [OddList[2*i+1],OddList[2*i]]
            for j in range(len(PATH)):
                if OddList[2*i] == PATH[j][1]:
                    PATH.insert(j+1,repeathPathA)
                    PATH.insert(j+2,repeathPathB)
                    break
        if Graph[OddList[2*i]][OddList[2*i+1]] == 0:
            distance,djPath = dijkstra(OriginGraph,OddList[2*i])
            pathList = djPath[OddList[2*i]][OddList[2*i+1]]
            pathList.insert(0,OddList[2*i])
            for k in range(len(PATH)):
                if OddList[2*i] == PATH[k][0] and OddList[2*i+1] == PATH[k][1]:
                    dj = [OddList[2*i],OddList[2*i+1]]
                    PATH.remove(dj)
                    addPath(PATH,pathList,k)
                    break
                if OddList[2*i] == PATH[k][1] and OddList[2*i+1] == PATH[k][0]:
                    dj = [OddList[2*i+1],OddList[2*i]]
                    PATH.remove(dj)
                    pathList.reverse()
                    addPath(PATH,pathList,k)
                    break

def splitPath(path,number):
    result = {}
    All = []
    order = list(path.keys())
    if len(order) < number:
        n = len(order)
    else:
        n = number
    a = round(len(order)/n)
    lists = []
    for i in range(n):
        tmp = []
        if i == n-1:
            tmp = order[i*a:]
        else:
            tmp = order[i*a:(i+1)*a]
        lists.append(tmp)
    j = 1
    for cList in lists:
        tmpPath = {}
        tmpPath['name'] = "%s号线"%(j)
        tmpPath['geometryType'] = 'line'
        tmpPath['geometry'] = []
        for k in cList:
            tmpNode = []
            tmpNode.append(float(path[k]['lon']))
            tmpNode.append(float(path[k]['lat']))
            tmpPath['geometry'].append(tmpNode)
        j += 1
        All.append(tmpPath)
    result['paths'] = All
    return result
            
    
#def handleRemain(remainList,LIST):
#    if len(remainList) == 2:
#        return 
#    tmpRemainList = combinaOddVertex(remainList)
#    print(tmpRemainList)
#    for List in tmpRemainList:
#        tmpList = list(set(remainList) - set(List))
#        print(List,tmpList)
#        LIST.append(List)
#        LIST.append(tmpList)
#        handleRemain(tmpList,LIST)

#OriginGraph= [
#[gigantic,3,18,11,gigantic,gigantic,gigantic,gigantic,gigantic,gigantic,gigantic],
#[7,gigantic,gigantic,9,6,gigantic,20,gigantic,gigantic,gigantic,gigantic],
#[31,gigantic,gigantic,22,gigantic,gigantic,gigantic,gigantic,gigantic,gigantic,gigantic],
#[10,4,33,gigantic,gigantic,17,12,gigantic,gigantic,gigantic,gigantic],
#[gigantic,16,gigantic,gigantic,gigantic,23,9,gigantic,gigantic,gigantic,gigantic],
#[gigantic,gigantic,gigantic,19,11,gigantic,7,4,gigantic,gigantic,gigantic],
#[gigantic,21,gigantic,31,22,15,gigantic,gigantic,gigantic,gigantic,gigantic],
#[gigantic,gigantic,gigantic,gigantic,gigantic,16,gigantic,gigantic,gigantic,17,gigantic],
#[gigantic,gigantic,gigantic,gigantic,gigantic,gigantic,gigantic,gigantic,gigantic,19,gigantic],
#[gigantic,gigantic,gigantic,gigantic,gigantic,gigantic,gigantic,3,2,gigantic,11],
#[gigantic,gigantic,gigantic,gigantic,gigantic,gigantic,gigantic,gigantic,gigantic,9,gigantic]
#]

if __name__ == '__main__':
    number = getparams(sys.argv[1:])
    result = getMySql(mysqlHost,mysqlUser,mysqlPW,mysqlDB)
    createOriginGraph(result)
    v_count = len(OriginGraph)
    calculateGraph = replicateGraph()
    floydQarshall(calculateGraph)
    Graph = createRelationMap()
    #print(Graph)
    GACalculateGraph = replicateGraph()
    floydQarshall(GACalculateGraph)
    #print(GACalculateGraph)
    #print(calculateGraph)
    oddList = findOddVertex()
    #print(oddList)
    #将奇点列表传入GA算法中,返回一个新的序列对
    GAobject = Scavenger(GACalculateGraph,oddList)
    GAOddList = GAobject.solve(GACalculateGraph,oddList)
    #print(GAOddList)
    startVertex,endVertex = findGAStartVertex(GAOddList)
    #print(GAOddList)
    GAGraph = GANewRelationMap(GAOddList)
    Path = []
    fleuryAlgorithm(startVertex,Path,GAGraph)
    #print(Path)
    reorganizePath(Path,GAOddList,Graph)
    #print(Path)
    final = getvertex(mysqlHost,mysqlUser,mysqlPW,mysqlDB,Path)
    #print(final)
    print(json.dumps(splitPath(final,number)))
